<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>bandwr</title>
  </head>
  <body bgcolor="#FFFFFF">
    <center>Scilab function</center>
    <div align="right">Last update : September 1996</div>
    <p>
      <b>bandwr</b> -  bandwidth reduction for a sparse matrix</p>
    <h3>
      <font color="blue">Calling Sequence</font>
    </h3>
    <dl>
      <dd>
        <tt>[iperm,mrepi,prof,ierr] = bandwr(sp,[iopt])  </tt>
      </dd>
      <dd>
        <tt>[iperm,mrepi,prof,ierr] = bandwr(lp,ls,n,[iopt])  </tt>
      </dd>
    </dl>
    <h3>
      <font color="blue">Parameters</font>
    </h3>
    <ul>
      <li>
        <tt>
          <b>sp</b>
        </tt>: sparse matrix</li>
      <li>
        <tt>
          <b>lp</b>
        </tt>: integer row vector</li>
      <li>
        <tt>
          <b>ls</b>
        </tt>: integer row vector</li>
      <li>
        <tt>
          <b>n</b>
        </tt>: integer</li>
      <li>
        <tt>
          <b>iopt</b>
        </tt>: integer</li>
      <li>
        <tt>
          <b>iperm</b>
        </tt>: integer row vector</li>
      <li>
        <tt>
          <b>mrepi</b>
        </tt>: integer row vector</li>
      <li>
        <tt>
          <b>prof</b>
        </tt>: integer row vector</li>
      <li>
        <tt>
          <b>ierr</b>
        </tt>: integer</li>
    </ul>
    <h3>
      <font color="blue">Description</font>
    </h3>
    <p>
      <tt>
        <b>bandwr</b>
      </tt> solves the problem of bandwidth reduction for a sparse
    matrix: the matrix is supposed to be upper triangular with a full
    diagonal (it is easy to complete a non symmetric matrix, and then
    discards the added terms).</p>
    <p>
    In the first calling sequence, <tt>
        <b>sp</b>
      </tt> denotes a
    sparse matrix; the optional argument <tt>
        <b>iopt</b>
      </tt> is 0 or 1:  1 if
    reducing  the profile of the matrix is more important than reducing 
    the bandwidth and 0 if bandwidth reduction is most important.</p>
    <p>
    The second calling sequence corresponds to the description of a graph:
    <tt>
        <b>lp</b>
      </tt>  is a row vector, pointer array of the adjacency lists
    description  of a graph (its size is the number of nodes of the graph + 1);
    <tt>
        <b>ls</b>
      </tt> is a  row vector, node array of the adjacency lists
    description (its size is the number of edges of the graph i.e. the
    number of non-zero terms of the corresponding sparse matrix).
    <tt>
        <b>n</b>
      </tt> is the number of nodes (dimension of <tt>
        <b>sp</b>
      </tt>).</p>
    <p>
      <tt>
        <b>iperm</b>
      </tt> is the permutation vector for reordering the rows
    and columns 
    which reduces the bandwidth and/or profile (new numbering of the nodes
    of the graph);
    <tt>
        <b>mrepi</b>
      </tt> is the inverse permutation (mrepi(iperm) is the identity).
    <tt>
        <b>prof</b>
      </tt> is the array giving the profile of the sparse matrix
    after the bandwidth reduction if <tt>
        <b>iopt</b>
      </tt> is 1. If <tt>
        <b>iopt</b>
      </tt> is 0 
    this array is zero except for the first term giving the bandwidth.
    The simple command <tt>
        <b>max(prof(2:$)-prof(1:($-1)))</b>
      </tt> returns
    the bandwidth of the matrix.
    <tt>
        <b>ierr</b>
      </tt> is an integer indicating an error if its value is not zero.</p>
    <h3>
      <font color="blue">Examples</font>
    </h3>
    <pre>

ta=[2  1 3 2 2 4 4 5 6 7 8 8 9 10 10 10 10 11 12 13 13 14 15 16 16 17 17];
he=[1 10 2 5 7 3 2 4 5 8 6 9 7 7 11 13 15 12 13  9 14 11 16 1 17 14 15];
g=make_graph('foo',0,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
// THE GRAPH
show_graph(g);
a=graph_2_mat(g,'node-node');
ww=tril(a)'+eye();
ww1=full(ww);
xset('window',1)
hist3d((ww1+tril(ww1',-1)+tril(ww1,-1)'),52,85); 
// BANDWIDTH REDUCTION FOR THE MATRIX
[iperm,mrepi,prof,ierr]=bandwr(ww);
max(prof(2:$)-prof(1:($-1)))
// GRAPH WITH THE NEW NUMBERING
g2=g;g2('node_name')=string(iperm);
show_graph(g2,'new')
// NEW MATRIX
n=g('node_number');
yy=ww1(mrepi,mrepi);
xset('window',3)
hist3d((yy+tril(yy',-1)+tril(yy,-1)'),52,85); 
// STARTING WITH THE SAME MATRIX
[ij,v,mn]=spget(ww);
g1=make_graph('foo',0,n,ij(:,1)',ij(:,2)');
g1('node_x')=g('node_x');g1('node_y')=g('node_y');
// GRAPH
//show_graph(g1,'rep');
[lp,la,ls] = adj_lists(1,n,g1('tail'),g1('head'));
[iperm,mrepi,prof,ierr]=bandwr(lp,ls,n,0);
g2=g;g2('node_name')=string(iperm);
show_graph(g2,'new');
 
  </pre>
  </body>
</html>
